/**
 * @file   RBIntervalTree.h
 * @author LiZhiqi
 * @date   Sat Dec 19 14:02:34 2020
 * 
 * @brief  A realization of interval tree 
 *         based on red-black tree.
 * 
 */

#ifndef MGGS__RBIT
#define MGGS__RBIT

#include "IntervalTree.h"

template <class TYPE>
class RBIntervalTree : public IntervalTree<TYPE>{
 public:
  typedef typename IntervalTree<TYPE>::Node Node;
  RBIntervalTree(TYPE _low, TYPE _high) : IntervalTree<TYPE>(_low,_high){this->root->color = BLACK;};
  RBIntervalTree(){};
  void insert(Node *_x);
  void insert(TYPE _low, TYPE _high);
  void del(Node *_x);
  void del(TYPE _low, TYPE _high);
  void Interval_Search(TYPE _low, TYPE _high);
};

template <class TYPE>
void RBIntervalTree<TYPE>::insert(Node *_x){
  IntervalTree<TYPE>::insert(_x);
  if (_x->parent == NULL || _x->parent->color==BLACK ){
    this->root->color = BLACK;
  }
  else{
  while (_x->parent != NULL && _x->color == RED){
    if (_x->parent == _x->parent->parent->lc){
      if (_x->parent->parent->rc != NULL && _x->parent->parent->rc->color == RED ){
        Node *y = _x->parent->parent->rc;
	_x->parent->color = y->color = BLACK;
	_x->parent->parent->color = RED;
	_x = _x->parent->parent;
	if (_x->parent == NULL || _x->parent->color == BLACK)
	  break;
	else;
      }
       else{
	  if (_x == _x->parent->rc){
	     this->LeftRotate(_x->parent);
	     _x = _x->lc;
	     }
	  this->RightRotate(_x->parent->parent);
	  _x->parent->color = BLACK;
	  _x->parent->rc->color = RED;
	  _x = _x->parent;
	  }
	}
     else if (_x->parent == _x->parent->parent->rc){
       if (_x->parent->parent->lc != NULL && _x->parent->parent->lc->color == RED){
          Node *y = _x->parent->parent->lc;
	  _x->parent->color = y->color = BLACK;
	  _x->parent->parent->color = RED;
	  _x = _x->parent->parent;
	  if (_x->parent == NULL || _x->parent->color == BLACK)
	     break;
	  else;
       }
	else{
	  if (_x == _x->parent->lc){
	     this->RightRotate(_x->parent);
	     _x = _x->rc;
	     }
	  this->LeftRotate(_x->parent->parent);
	  _x->parent->color = BLACK;
	  _x->parent->lc->color = RED;
	  _x = _x->parent;
	  }
	}
    }
    this->root->color = BLACK;
  }
}

template <class TYPE>
void RBIntervalTree<TYPE>::insert(TYPE _low, TYPE _high){
  Node *p = new Node(_low,_high);
  insert(p);
}

template <class TYPE>
void RBIntervalTree<TYPE>::del(Node *_x){
  int t=0;
  Node *y = _x;
  bool original_color_y = y->color;
  Node z=Node(0,0);
  Node *x=&z;
  x->color = BLACK;
  if (_x != NULL){
    if (_x->lc == NULL && _x->rc != NULL){
      x = _x->rc;
      this->transplant(_x, _x->rc);
      this->allupdate_max(_x->parent);
    }
    else if (_x->rc == NULL && _x->lc != NULL){
      x = _x->lc;
      this->transplant(_x, _x->lc);
      this->allupdate_max(_x->parent);
    }
    else if (_x->rc ==NULL && _x->lc == NULL){
      if (y == y->parent->lc){
	y = y->parent;
	y->lc = x;
	x->parent = y;
	x->lc = x->rc = NULL;
	t=1;
	this->allupdate_max(y);
      }
      else{
	y = y->parent;
	y->rc = x;
	x->parent = y;
	x->lc = x->rc = NULL;
	t=1;
	this->allupdate_max(y);
      }
    }
    else{
      y =IntervalTree<TYPE>::min(_x->rc);
      Node* u = y->parent;
      original_color_y = y->color;
      if (y->rc != NULL)
	x = y->rc;
      else{
	y->rc = x;
	x->parent = y;
	x->lc = x->rc = NULL;
	t=1;
      }
      if (y->parent != _x){
	this->transplant(y, y->rc);
	y->rc = _x->rc;
	y->rc->parent = y;
      }
      this->transplant(_x, y);
      y->lc = _x->lc;
      y->lc->parent = y;
      y->color = _x->color;
      this->allupdate_max(u);
    }
  }
  if (original_color_y == BLACK)
    while (x != this->root && x->color == BLACK){
      if (x == x->parent->lc){
	Node *w = x->parent->rc;
	if (w->color == RED){
	  w->color = BLACK;
	  x->parent->color = RED;
	  this->LeftRotate(x->parent);
	  w = x->parent->rc;
	}
	if (w->lc->color == BLACK && w->rc->color == BLACK){
	   w->color = RED;
    	   x = x->parent;
	   t = 0;
	}
	else{
	  if (w->rc->color == BLACK){
	    w->lc->color = BLACK;
	    w->color = RED;
	    this->RightRotate(w);
	    w = x->parent->rc;
	  }
	  w->color = x->parent->color;
	  x->parent->color = BLACK;
	  w->rc->color = BLACK;
	  this->LeftRotate(x->parent);
	  x->parent->lc = NULL;
	  x = this->root;
	  t = 0;
	}
    }
      else{
	Node *w = x->parent->lc;
	if (w->color == RED){
	  w->color = BLACK;
	  x->parent->color = RED;
	  this->RightRotate(x->parent);
	  w = x->parent->lc;
	}
	if (w->lc->color == BLACK && w->rc->color == BLACK){
	   w->color = RED;
    	   x = x->parent;
	   x->lc = NULL;
	   t = 0;
	}
	else{
	  if (w->lc->color == BLACK){
	    w->rc->color = BLACK;
	    w->color = RED;
	    this->LeftRotate(w);
	    w = x->parent->lc;
	  }
	  w->color = x->parent->color;
	  x->parent->color = BLACK;
	  w->lc->color = BLACK;
	  this->RightRotate(x->parent);
	  x->parent->rc = NULL;
	  x = this->root;
	  x->rc = NULL;
	  t = 0;
	}
      }
   }
  if (t == 1){
    if (x == x->parent->lc)
      x->parent->lc = NULL;
    else
      x->parent->rc = NULL;
  }
  else
    x->color = BLACK; 
  delete _x;
}

template <class TYPE>
void RBIntervalTree<TYPE>::del(TYPE _low, TYPE _high){
  Node* p = IntervalTree<TYPE>::tree_search(_low,_high);
  this->del(p);
}

template <class TYPE>
void RBIntervalTree<TYPE>::Interval_Search(TYPE _low, TYPE _high){
  IntervalTree<TYPE>::test_Interval_Search(_low,_high);
}

#else
//DO NOTHING.
#endif




